An essential semiconductor device is semiconductor memory, such as a random access memory (RAM) device. A RAM device allows a memory circuit to execute both read and write operations on its memory locations. Typical examples of RAM devices include dynamic random access memory (DRAM) and static random access memory (SRAM).
Another form of memory is the content addressable memory (CAM) device. A CAM is a memory device that accelerates any application requiring fast searches of a database, list, or pattern, such as in database machines, image or voice recognition, or computer and communication networks. Searches in CAM devices are performed by simultaneously comparing the desired information (i.e., data in a comparand register) against an entire list of pre-stored entries. As a result of their unique searching algorithm, CAM devices are frequently employed in network equipment, particularly routers and switches, computer systems and other devices that require rapid content searching.
FIG. 1 is a block diagram of an exemplary CAM device 100, which includes a CAM array 110 for storing the database; a match detection circuit 120, which may be embedded in CAM array 110, for detecting matches; a comparand register 160 for storing data to be compared with data stored in array 110; optionally a priority encoder 130 for selecting and outputting an indication of which of the array locations matching data in the comparand register 160 has a highest or lowest priority; and an address encoder 170 for decoding an address output associated with the priority output of the priority encoder 130. The CAM device also includes a controller 140, for controlling the operation of the CAM array 110, match detection logic 120, and priority encoder 130, as well as for interfacing the CAM device 100 to other devices via the data 150a, address 150b, and control 150c lines. Commercially available CAM devices may support, for example, searching a 136-bit wide data sample against a database having up to 16,384 entries. Commercially available CAM devices may be searched at rates up to 100 million searches per second. This ability for CAMs to quickly search relatively wide data words against relatively large databases at high speeds makes them highly useful.
In order to perform a memory search in the above-identified manner, CAMs are organized differently than other memory devices (e.g., DRAM and SRAM). For example, data is stored in a RAM in a particular location, called an address. During a memory access, the user supplies an address and reads into or gets back the data at the specified address. In a CAM, however, data is stored in locations in a somewhat random fashion. The locations can be selected by an address bus, or the data can be written into the first empty memory location. Every location could have a pair of status bits that keep track of whether the location is storing valid information or is empty and available for writing.
Information stored in a CAM memory location is found by comparing it with an input data value held in the comparand register. A local match detection circuit can compare all or some of its bits with the input data value. When the content stored in a CAM memory location does not match the data in the comparand register, a local match detection circuit returns a no match indication. When the content stored in a CAM memory location matches the data in the comparand register, the local match detection circuit returns a match indication. If one or more local match detect circuits return a match indication, the CAM device returns a “match” indication. If there are multiple matches, the CAM may also return a multiple match (MMatch) indication. Otherwise, the CAM device returns a “no match” indication. In addition, the CAM may return an address associated with the desired match data, or if a plurality of memory locations has match data, an address associated with a highest or lowest priority match can be identified with the priority encoder. Thus, with a CAM, the user supplies the data and gets back an address when there is a match.
FIG. 3 is a flowchart describing a conventional test procedure associated with CAM device 100 in which unique data and a search command is applied to CAM device 100 to determine if a match occurs. If a match occurs, the address where the match occurs must be determined to verify whether or not a memory location of CAM device 100 is operating correctly. At segment 1000, a unique data entry is written to each memory address in an array of CAM device 100. At segment 1100, a search of the CAM device 100 is initiated, by applying a search command, which searches for a unique data entry that should reside in the CAM array. At segment 1200, a determination of whether the test data resides in the CAM array occurs. If the data is found in the CAM array at segment 1200, CAM device 100 is queried at segment 1300 to retrieve the address at which the data was found. If the data is not found in the CAM array, the procedure continues to segment 1450 where the failing memory location is marked for subsequent repair by the memory tester.
As illustrated at segment 1400, a determination of whether the test data was found at the correct address occurs. The address retrieved at segment 1300 is compared to the address where the data was written to determine if the data was found at the correct memory location. If the address retrieved is the same as the written address then CAM 100 has functioned properly. If the addresses are not the same, then an error has occurred at the written address, which is marked for subsequent repair as shown at segment 1450. In addition, the retrieved address could be marked for repair. As shown in segment 1500, this procedure is repeated for all memory locations intended to be tested in CAM device 100 by returning to segment 1100 once an individual memory location has been tested. At segment 1600, once the testing is complete, the memory locations of the CAM device 100 that failed the test procedure are repaired and retested to validate the repair of the memory location.
Testing of CAM devices is extremely time consuming and costly. In particular, CAMs have to be tested for their ability to match a test data value with different stored data values. The conventional means of testing CAM devices is performed by loading the CAM memory locations with known data and the repetitive inputting of data as a search argument and outputting the address associated with the location where the data is found (if the data is stored in the CAM). This repetitive searching for matching CAM entries in successive operational clock cycles is illustrated by the timing diagram in FIG. 2.
Accordingly, there is a need for a more efficient and less expensive means of testing CAM devices.